<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Introduction</title>
<link rel="stylesheet" href="../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="Chapter 1. Coroutine2">
<link rel="up" href="../index.html" title="Chapter 1. Coroutine2">
<link rel="prev" href="overview.html" title="Overview">
<link rel="next" href="motivation.html" title="Motivation">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td>
<td align="center"><a href="../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="overview.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="motivation.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="coroutine2.intro"></a><a class="link" href="intro.html" title="Introduction">Introduction</a>
</h2></div></div></div>
<h4>
<a name="coroutine2.intro.h0"></a>
      <span class="phrase"><a name="coroutine2.intro.definition"></a></span><a class="link" href="intro.html#coroutine2.intro.definition">Definition</a>
    </h4>
<p>
      In computer science routines are defined as a sequence of operations. The execution
      of routines forms a parent-child relationship and the child terminates always
      before the parent. Coroutines (the term was introduced by Melvin Conway <a href="#ftn.coroutine2.intro.f0" class="footnote" name="coroutine2.intro.f0"><sup class="footnote">[1]</sup></a>), are a generalization of routines (Donald Knuth <a href="#ftn.coroutine2.intro.f1" class="footnote" name="coroutine2.intro.f1"><sup class="footnote">[2]</sup></a>). The principal difference between coroutines and routines is that
      a coroutine enables explicit suspend and resume of its progress via additional
      operations by preserving execution state and thus provides an <span class="bold"><strong>enhanced
      control flow</strong></span> (maintaining the execution context).
    </p>
<h4>
<a name="coroutine2.intro.h1"></a>
      <span class="phrase"><a name="coroutine2.intro.how_it_works"></a></span><a class="link" href="intro.html#coroutine2.intro.how_it_works">How
      it works</a>
    </h4>
<p>
      Functions foo() and bar() are supposed to alternate their execution (leave
      and enter function body).
    </p>
<p>
      <span class="inlinemediaobject"><img src="../../../../../libs/coroutine2/doc/images/foo_bar.png" align="middle" alt="foo_bar"></span>
    </p>
<p>
      If coroutines were called exactly like routines, the stack would grow with
      every call and would never be popped. A jump into the middle of a coroutine
      would not be possible, because the return address would be on top of stack
      entries.
    </p>
<p>
      The solution is that each coroutine has its own stack and control-block (<a href="../../../../../libs/context/doc/html/context/cc.html#implementation" target="_top">fcontext_t</a>
      from <span class="bold"><strong>Boost.Context</strong></span>). Before the coroutine
      gets suspended, the non-volatile registers (including stack and instruction/program
      pointer) of the currently active coroutine are stored in the coroutine's control-block.
      The registers of the newly activated coroutine must be restored from its associated
      control-block before it is resumed.
    </p>
<p>
      The context switch requires no system privileges and provides cooperative multitasking
      convenient to C++. Coroutines provide quasi parallelism. When a program is
      supposed to do several things at the same time, coroutines help to do this
      much more simply and elegantly than with only a single flow of control. The
      advantages can be seen particularly clearly with the use of a recursive function,
      such as traversal of binary trees (see example 'same fringe').
    </p>
<h4>
<a name="coroutine2.intro.h2"></a>
      <span class="phrase"><a name="coroutine2.intro.characteristics"></a></span><a class="link" href="intro.html#coroutine2.intro.characteristics">characteristics</a>
    </h4>
<p>
      Characteristics <a href="#ftn.coroutine2.intro.f2" class="footnote" name="coroutine2.intro.f2"><sup class="footnote">[3]</sup></a> of a coroutine are:
    </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
          values of local data persist between successive calls (context switches)
        </li>
<li class="listitem">
          execution is suspended as control leaves coroutine and is resumed at certain
          time later
        </li>
<li class="listitem">
          symmetric or asymmetric control-transfer mechanism; see below
        </li>
<li class="listitem">
          first-class object (can be passed as argument, returned by procedures,
          stored in a data structure to be used later or freely manipulated by the
          developer)
        </li>
<li class="listitem">
          stackful or stackless
        </li>
</ul></div>
<p>
      Coroutines are useful in simulation, artificial intelligence, concurrent programming,
      text processing and data manipulation, supporting the implementation of components
      such as cooperative tasks (fibers), iterators, generators, infinite lists,
      pipes etc.
    </p>
<h4>
<a name="coroutine2.intro.h3"></a>
      <span class="phrase"><a name="coroutine2.intro.execution_transfer_mechanism"></a></span><a class="link" href="intro.html#coroutine2.intro.execution_transfer_mechanism">execution-transfer
      mechanism</a>
    </h4>
<p>
      Two categories of coroutines exist: symmetric and asymmetric coroutines.
    </p>
<p>
      An asymmetric coroutine knows its invoker, using a special operation to implicitly
      yield control specifically to its invoker. By contrast, all symmetric coroutines
      are equivalent; one symmetric coroutine may pass control to any other symmetric
      coroutine. Because of this, a symmetric coroutine <span class="emphasis"><em>must</em></span>
      specify the coroutine to which it intends to yield control.
    </p>
<p>
      <span class="inlinemediaobject"><img src="../../../../../libs/coroutine2/doc/images/foo_bar_seq.png" align="middle" alt="foo_bar_seq"></span>
    </p>
<p>
      Both concepts are equivalent and a fully-general coroutine library can provide
      either symmetric or asymmetric coroutines.
    </p>
<h4>
<a name="coroutine2.intro.h4"></a>
      <span class="phrase"><a name="coroutine2.intro.stackfulness"></a></span><a class="link" href="intro.html#coroutine2.intro.stackfulness">stackfulness</a>
    </h4>
<p>
      In contrast to a stackless coroutine a stackful coroutine can be suspended
      from within a nested stackframe. Execution resumes at exactly the same point
      in the code where it was suspended before. With a stackless coroutine, only
      the top-level routine may be suspended. Any routine called by that top-level
      routine may not itself suspend. This prohibits providing suspend/resume operations
      in routines within a general-purpose library.
    </p>
<h4>
<a name="coroutine2.intro.h5"></a>
      <span class="phrase"><a name="coroutine2.intro.first_class_continuation"></a></span><a class="link" href="intro.html#coroutine2.intro.first_class_continuation">first-class
      continuation</a>
    </h4>
<p>
      A first-class continuation can be passed as an argument, returned by a function
      and stored in a data structure to be used later. In some implementations (for
      instance C# <span class="emphasis"><em>yield</em></span>) the continuation can not be directly
      accessed or directly manipulated.
    </p>
<p>
      Without stackfulness and first-class semantics, some useful execution control
      flows cannot be supported (for instance cooperative multitasking or checkpointing).
    </p>
<div class="footnotes">
<br><hr style="width:100; text-align:left;margin-left: 0">
<div id="ftn.coroutine2.intro.f0" class="footnote"><p><a href="#coroutine2.intro.f0" class="para"><sup class="para">[1] </sup></a>
        Conway, Melvin E.. "Design of a Separable Transition-Diagram Compiler".
        Commun. ACM, Volume 6 Issue 7, July 1963, Article No. 7
      </p></div>
<div id="ftn.coroutine2.intro.f1" class="footnote"><p><a href="#coroutine2.intro.f1" class="para"><sup class="para">[2] </sup></a>
        Knuth, Donald Ervin (1997). "Fundamental Algorithms. The Art of Computer
        Programming 1", (3rd ed.)
      </p></div>
<div id="ftn.coroutine2.intro.f2" class="footnote"><p><a href="#coroutine2.intro.f2" class="para"><sup class="para">[3] </sup></a>
        Moura, Ana Lucia De and Ierusalimschy, Roberto. "Revisiting coroutines".
        ACM Trans. Program. Lang. Syst., Volume 31 Issue 2, February 2009, Article
        No. 6
      </p></div>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2014 Oliver Kowalke<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="overview.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="motivation.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
